The invention relates generally to the field of digital networking systems, and more particular to systems and methods for controlling the transfer of message packets over a digital network. The invention particularly provides an system and method by which message packets which are provided for transfer using a xe2x80x9cconnectionlessxe2x80x9d packet transfer methodology can be transferred over a network using a virtual circuit packet transfer methodology.
Digital networks have been developed to facilitate the transfer of information, including data and programs, among digital computer systems and numerous other types of devices. A variety of types of networks have been developed and implemented using diverse information transfer methodologies. In modem networks, information is transferred through a mesh of switching nodes which are interconnected by communication links in a variety of patterns. The mesh interconnection pattern can allow for a number of paths to be available through the network from each computer system or other device which may transmit information as a source device, to another computer system or other device, which is to receive the information as a destination device, so that if one switching node or communication link is congested or inoperative, the information can be routed around the congested or inoperative portion of the network.
Information transferred from a source device to a destination device is generally transferred in the form of fixed- or variable-length packets, which are transferred through the network in accordance with one of several general packet transfer methodologies. In one packet transfer methodology, termed a xe2x80x9cconnectionlessxe2x80x9d data transfer methodology, each information packet that is transmitted by a source device to a destination device includes, in addition to the information to be transferred, destination address information which identifies the particular device that is to receive the packet, along with an identifier identifying the particular switching node to which the destination device is connected. Each switching node in the network is provided with a database that stores network topology information, which describes the entire topology of the network, and a routing table that provides, among other information, routing information identifying the path to be taken from the switching node to any other switching node in the network. When a switching node receives a packet that is to be transferred to a particular destination device, it (that is, the switching node) will use the routing table to identify a communication link over which the packet is to be transmitted.
Each switching node that receives the packet will perform a similar operation, until the packet is transferred to a switching node which is connected to the destination device. At that point, the switching node will identify the particular communication link connected between it and the destination device, and will transfer the packet to the destination device. Similar operations occur for each packet transferred through the network, so that each switching node will make a routing decision, to identify a particular communication link over which it is to transfer each packet that it receives, for each packet. The routing decision is overhead that may delay delivery of packets to their respective destinations, but if the packet traffic between particular source and destination devices is relatively low, which may be the case if the network allows relatively large packets to be transferred, and if the delay in delivery is not critical, the connectionless methodology can provide good service. On the other hand, since each switching node makes a routing decision effectively xe2x80x9con-the-flyxe2x80x9d for each packet, if a portion of the network becomes congested or otherwise unavailable, each switching node can easily take that into account in its routing decision.
Another packet transfer methodology alleviates the necessity of requiring the switching nodes to make an xe2x80x9con the flyxe2x80x9d routing decision for each of the packets which they receive. In this packet transfer methodology, packets are transferred through the network""s switching nodes over constructs which are generally termed xe2x80x9cvirtual circuits,xe2x80x9d xe2x80x9cvirtual connectionsxe2x80x9d and the like (generally, xe2x80x9cvirtual circuitsxe2x80x9d). When a source device wishes to transfer information to a destination device, initially a preliminary operation will be performed to establish a virtual circuit over communication links defining a path from the source device, through a series of switching nodes to the destination device. As with the connectionless methodology, each switching node that operates using the virtual circuit methodology may include a network topology database that stores network topology information, which describes the entire topology of the network as well the identifiers for the various destination devices and the switching nodes to which they are connected, which network topology database can be used to assist in identifying a path through the various switching nodes of the network for the virtual circuit.
In addition to the network topology database, each switching node in the virtual circuit methodology will also be provided with a virtual circuit database that associates each of the virtual circuits maintained by the respective switching node with a particular one of the communication links. After a virtual circuit is established, the source device can transfer packets using the virtual circuit database Each packet will include, as well as the data to be transferred, an identifier that identifies the particular virtual circuit to be used in transferring the packet. The source device will initially transfer the packet to the switching node connected thereto, and that switching node will use virtual circuit identifier and the virtual circuit database to identify a communication link over which it (that is, the switching node) is to transfer the packet. These operations will be performed for each switching node along the virtual circuit which receives the packet. When the last switching node along the virtual circuit receives the packet, that switching node will transfer the packet to the particular destination device associated with the virtual circuit. These operations will be repeated for each of the packets transferred from the source device to the destination device. In addition, similar operations may also be performed in connection with packets which the destination device may transfer to the source device, since a single virtual circuit, once established, may be used to transfer packets in both directions between the original source device and the original destination device.
At the end of a communications session between the source device and the destination device, in which one or a number of packets may be transferred, the devices may close the virtual circuit. In that operation, packets are transferred between the source and destination devices which, among other things, can enable the switching nodes along the virtual circuit to expunge the virtual circuit information relating to the particular virtual circuit being closed from their respective virtual circuit databases. Thereafter, the virtual circuit identifier and other resources, including the entries in the respective virtual circuit databases associated with the closed virtual circuit, can be used for other virtual circuits.
There are several benefits of using the virtual circuit methodology in some environments. One benefit is that, in the virtual circuit methodology, routing decisions at each switching node need only be made while a virtual circuit is being established, instead of each time a packet is received which is to be transferred to a particular destination device as in the connectionless methodology. However, as indicated above, there is some overhead in the message traffic and routing decisions which are required to establishing a virtual circuit and in closing the virtual circuit at the end of the communications session. This overhead can be effectively amortized if the network is such that a significant amount of packet traffic between source devices and destination devices is expected during a communication session. However, if transfer of only a few packets are expected during most sessions, the overhead may not be satisfactorily amortized.
In addition, in the virtual circuit methodology, the switching nodes need to maintain the additional virtual circuit database, whose capacity places an effective limit on the number of simultaneous virtual circuits that a single switching node can handle. This problem can be exacerbated since the various pairs of source and destination devices can have multiple virtual circuits therebetween, information for each of which will need to be provided in the virtual circuit database.
A further problem that can arise in a network constructed in accordance with the virtual circuit methodology is as follows. If a disruption occurs in the network, which may occur if, for example, a particular communication link interconnecting switching nodes malfunctions, the virtual circuits which use the particular communication link will need to be re-established over other communication links, requiring the various devices and switching nodes to repeat the establishment phase before the virtual circuits can again be used, which, in turn, can delay communications. In a network constructed in accordance with the connectionless methodology, since routing decisions are made xe2x80x9con the fly,xe2x80x9d a network disruption may not result in a similar communication delay.
The invention provides a new and improved system and method for transferring packets in a xe2x80x9cconnectionlessxe2x80x9d network.
In brief summary, the new network comprises a plurality of devices interconnected by a plurality of switching nodes. At least one device, as a source device, generates device packets for transfer to other devices, as destination devices, with each device packet including an address portion including an address identifying at least one of the destination devices. The switching nodes establish respective virtual circuits thereover for transferring virtual circuit packets from at least one the switching node, as an originating switching node, which is connected to the source device, to others of the switching nodes, as respective terminating switching nodes, each of which is connected to a destination device. The originating switching node receives each device packet from the source device and generates a respective virtual circuit packet therefor, each virtual circuit packet including a virtual circuit identifier identify one of the virtual circuits over which the virtual circuit packet is to be transferred, and transferring the respective virtual circuit packet over the virtual circuit. Successive switching nodes associated with each virtual circuit, as intermediate switching nodes, receive the virtual circuit packets and use the virtual circuit identifier in each packet to determine routing for the virtual circuit packet. Each terminating switching node, upon receipt of a the virtual circuit packet, extract the device packet and, using the address identifying the destination device, transfer the device packet to the identified destination device.